package org.aplombh.java.awcing.basic.graph.bipartiteGraph;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 给定一个二分图，其中左半部 包含 n1 个点（编号 1∼n1），右半部 包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。
 * <p>
 * 数据保证任意一条边的两个端点都不可能在同一部分中。
 * <p>
 * 请你求出二分图的最大匹配数。
 * <p>
 * 二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
 * <p>
 * 二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
 * <p>
 * 输入格式
 * 第一行包含三个整数 n1、 n2 和 m。
 * <p>
 * 接下来 m 行，每行包含两个整数 u 和 v，表示左半部 点集中的点 u 和右半  部 点集中的点 v 之间存在一条边。
 * <p>
 * 输出格式
 * 输出一个整数，表示二分图的最大匹配数。
 * <p>
 * 数据范围
 * 1≤n1,n2≤500,
 * 1≤u≤n1,
 * 1≤v≤n2,
 * 1≤m≤105
 * 输入样例：
 * 2 2 4
 * 1 1
 * 1 2
 * 2 1
 * 2 2
 * 输出样例：
 * 2
 */
public class MaximumMatching_861 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n1 = scanner.nextInt();
        int n2 = scanner.nextInt();
        int m = scanner.nextInt();
        HungaryAlgorithm bipartiteGraph = new HungaryAlgorithm(n1, n2, m);
        while (m-- != 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            bipartiteGraph.add(a, b);
        }
        System.out.println(bipartiteGraph.match());
    }
}

class HungaryAlgorithm {
    public static final int N = 510, M = 100010;
    int n1, n2, m, idx;
    int[] h = new int[N];
    int[] e = new int[M];
    int[] ne = new int[M];
    int[] match = new int[N];
    boolean[] st = new boolean[N];

    public HungaryAlgorithm(int n1, int n2, int m) {
        this.n1 = n1;
        this.n2 = n2;
        this.m = m;
        Arrays.fill(h, -1);
    }

    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    int match() {
        int res = 0;
        for (int i = 0; i <= n1; i++) {
            Arrays.fill(st, false);
            if (find(i)) res++;
        }
        return res;
    }

    boolean find(int x) {

        for (int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                st[j] = true;
                // j还未匹配 或者  j已经匹配好的点可以换一个匹配 则将j的匹配换为x 可以换一个匹配
                if (match[j] == 0 || find(match[j])) {
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }
}